﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

public class Solution215
{
    //堆排序
    public int FindKthLargest(int[] nums, int k)
    {
        MakeBigHeap(nums);
        int len = nums.Length;
        for (int i = nums.Length - 1; i >= nums.Length - k; i--)
        {
            MySwap(nums, 0, i);
            len--;
            AdjustBigHeap(nums, 0, len);
        }


        return nums[nums.Length - k];

    }


    //构建大根堆

    void MakeBigHeap(int[] nums)
    {

        int len = nums.Length;

        for (int i = len / 2; i >= 0; i--)
        {

            AdjustBigHeap(nums, i, len);

        }

    }

    //小元素下坠,下坠到已经排序好的就不用动了
    private void AdjustBigHeap(int[] nums, int i, int needAdjustLen)
    {


        int left = 2 * i + 1;
        int right = 2 * i + 2;
        int bigger = i;
        if (left < needAdjustLen && nums[left] > nums[bigger])
        {

            bigger = left;

        }
        if (right < needAdjustLen && nums[right] > nums[bigger])
        {

            bigger = right;

        }
        if (bigger == i)//已经最大了
        {
            return;
        }
        MySwap(nums, i, bigger);

        AdjustBigHeap(nums, bigger, needAdjustLen);

    }

    private void MySwap(int[] nums, int i, int bigger)
    {
        int temp = nums[i];
        nums[i] = nums[bigger];
        nums[bigger] = temp;
    }
}

class Program215
{



    static void Main215(string[] args)
    {

        int[] nums = [3, 2, 1, 5, 6, 4];
        Solution215 solution = new Solution215();
        int res = solution.FindKthLargest(nums, 2);
        Console.WriteLine(res);
    }
}